Information symbols are transmitted over channels in most information, storage and communication devices. The channel can comprise, for example, a wired or wireless communication link between a transmitter or receiver, or an information path within a disk drive. More generally, any information path of limited bandwidth through which digital signals are transmitted may be defined as a channel. Such channels are subject to various types of distortion, e.g., additive noise and intersymbol interference. These distortions limit the data rate efficiencies for communication over such channels. Accordingly, much effort has been devoted to reducing the effect of such distortions in the channels. The obvious end goal is to decode symbols accurately. More specifically, the goal is to have low decoding error rates. A second and conflicting goal is to increase the ratio of data symbols to total channel symbols transmitted, i.e., the data rate.
Recent focus for joint equalization and decoding has been on iterative decoding schemes, and in particular, turbo coding schemes. These schemes are confidence building schemes in which an equalizer and decoder trade soft information in the form of symbol estimates until convergence is reached and hard decisions for symbols are output. These iterative schemes treat the channel contribution like an error correction code. The data symbols are generally permuted before transmission and are typically protected with a convolutional error correcting code. On the decoding side, soft information is exchanged between an error correction decoder and a channel decoder. However, all current implementations of these soft information exchange schemes use a forward/backward, Viterbi, or similar decoding algorithm for the decoding function. Specific examples are the forward/backward and soft output Viterbi algorithm for convolutional codes. In such decoding schemes, the complexity of the decoder is a design choice, but the complexity of a trellis based equalizer is a function of the length of the channel impulse response. This limits practical usefulness of the conventional decoding schemes to a class of channels having reasonably short impulse response lengths or small signal constellations.
The complex nature of conventional equalizing schemes in soft input exchange methods and devices also places certain physical limitations on devices which rely on such methods and devices for channel decoding. For example, there exist no solutions beyond one dimension for forward/backward and Viterbi algorithms. This dictates a one dimensional data stream, such as the stream obtained by a magnetic disk drive head or an optical disk drive. There is no significant physical reason for restriction to one-dimensional streams of data, but an as yet insurmountable hurdle for extension to higher dimensions is the lack of higher dimensional forward/backward and Viterbi algorithms. A decoding method with multi-dimensional decoding capability would free devices from the requirement of creating a one dimensional stream of data. For example, two dimensional regions of disk drives could be read simultaneously if two dimensional channel decoding is supported. The forward/backward and Viterbi algorithms used for data decoding are unable to handle the multidimensional task since multidimensional solutions are unknown.
Accordingly, there is a need for an improved method for decoding data received over a potentially noisy channel which addresses some or all of the aforementioned drawbacks. It is an object of the invention to provide such an improved method.